package com.shindo.novie.class04;

/**
 * 单双链表反转
 * 两个链表的反转都需要借助两个临时节点来记录当前游标的前后节点信息
 */
public class Code01_ReverseList {

    /**
     * 单链表
     */
    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            value = data;
        }
    }

    /**
     * 单链表反转方法
     * 方法最后要返回反转后的链表头指针
     * 注意pre 和 next 的移动，是算法的关键
     */
    public static Node reverseLinkList(Node head) {
        Node pre = null;
        Node next = null;
        while (head != null) {
            //记录下一跳的环境
            next = head.next;
            //链表指针方向反转-单链表只需要反转后指针
            head.next = pre;
            //当前节点向后移动
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 双链表
     */
    public static class DoubleNode {
        public int value;
        //后节点
        public DoubleNode next;
        //前节点
        public DoubleNode last;

        public DoubleNode(int data) {
            value = data;
        }
    }

    /**
     * 双向链表反转
     *
     * @param head 头节点
     * @return
     */
    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            //记录下一跳的环境
            next = head.next;
            //链表指针方向反转-双链表需要反转前后指针
            head.next = pre;
            head.last = next;
            //当前节点向后移动
            pre = head;
            head = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        //单链表验证
        Node node1 = new Node(1);
        node1.next = new Node(2);
        node1.next.next = new Node(3);

        Node head = reverseLinkList(node1);
        while (head != null) {
            System.out.println(head.value);
            head = head.next;
        }

    }
}
